Package edu.claflin.finder.algo

Class BronKerbosch

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.BronKerbosch

All Implemented Interfaces:

Processable<Graph,Graph>

public class BronKerbosch
extends Algorithm

Finds Maximum Cliques and Bicliques with Bron Kersboch Algorithm. https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	bipartite

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, counter, listener, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
BronKerbosch(ArgumentsBundle bundle)	Public constructor for initializing the Bron Kersbboch with default conditions.

Method Summary

Modifier and Type	Method	Description
static void	bronKerbosch(java.util.ArrayList<Graph> results, Graph r, Graph p, Graph x, Graph orig)	Recursive helper method to do the above.
static java.util.ArrayList<Graph>	bronKerboschBiclique(Graph graph)	Bipartite Bron Kerbosch algorithm that uses the above to find all complete bipartite graphs within a bipartite graph.
static java.util.ArrayList<Graph>	bronKerboschClique(Graph graph)	Given a graph, finds all complete subgraphs.
static java.util.ArrayList<Graph>	maximumBicliques(Graph graph)	Gets the Maximum Complete Bipartite Graphs by Node count from the input Graph using Bron-Kersboch.
static java.util.ArrayList<Graph>	maximumCliques(Graph graph)	Given a graph, finds all complete subgraphs, and then returns the largest one.
java.util.ArrayList<Graph>	process(Graph graph)	Processes data.
java.lang.String	toString()

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getPartiteNumber, removePropertyChangeListener, setGraphSortOrder, setPartiteNumber, setProgress

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

bipartite

private final boolean bipartite

Constructor Detail

BronKerbosch

public BronKerbosch(ArgumentsBundle bundle)

Public constructor for initializing the Bron Kersbboch with default conditions.

Parameters:

bundle - the ArgumentsBundle containing the instantiation arguments.

Method Detail

process

public java.util.ArrayList<Graph> process(Graph graph)

Processes data.
Finds most Subgraphs by performing a depth first search on the node tree. It is unknown if it finds all or only most of the subgraphs due to the nature of the algorithm. It is expected, however, that it would miss certain node groupings.

Parameters:

graph - the Graph object to search through.

Returns:

the ArrayList of Graph objects holding all found subgraphs.

bronKerbosch

public static void bronKerbosch(java.util.ArrayList<Graph> results,
                                Graph r,
                                Graph p,
                                Graph x,
                                Graph orig)

Recursive helper method to do the above.

Parameters:

results - result list. Passed between recursive calls to create output

r - graph r in wikipedia link

p - graph p in wikipedia link

x - graph x in wikipedia link

orig - original Graph containing edges

bronKerboschClique

public static java.util.ArrayList<Graph> bronKerboschClique(Graph graph)

Given a graph, finds all complete subgraphs.

Parameters:

graph - the graph

Returns:

an ArrayList of complete subgraphs, unordered

bronKerboschBiclique

public static java.util.ArrayList<Graph> bronKerboschBiclique(Graph graph)

Bipartite Bron Kerbosch algorithm that uses the above to find all complete bipartite graphs within a bipartite graph. This is done by adding edges between every node in both groups, using the above algorithm, and removing all the added edges later on. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!

Parameters:

graph - the bipartite graph

Returns:

array list of bipartite graphs

maximumCliques

public static java.util.ArrayList<Graph> maximumCliques(Graph graph)

Given a graph, finds all complete subgraphs, and then returns the largest one.

Parameters:

graph - the graph

Returns:

the largest complete subgraph (clique)

maximumBicliques

public static java.util.ArrayList<Graph> maximumBicliques(Graph graph)

Gets the Maximum Complete Bipartite Graphs by Node count from the input Graph using Bron-Kersboch.

Parameters:

graph - the input Graph

Returns:

the Maximum Complete Bipartite Graphs

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object